package com.uyong.study.algorithm.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 桶排序O(n), 非原地O(n),稳定
 * 
 * @author gonggy
 * @since 2019-01-30
 */
public class BucketSort implements ISort {

	@Override
	public void sort(int[] data) {
		if (data.length <= 0) {
			return;
		}

		int min = Arrays.stream(data).min().getAsInt();
		int max = Arrays.stream(data).max().getAsInt();
		if (min == max) {
			return;
		}

		int bucketNumber = (max - min) / data.length + 1; // 桶个数

		// 初始化桶
		List<ArrayList<Integer>> buckets = new ArrayList<>(bucketNumber);
		for (int i = 0; i < bucketNumber; i++) {
			buckets.add(new ArrayList<>());
		}

		// 将元素放到各自的桶里
		for (int element : data) {
			buckets.get((element - min) / data.length).add(element);
		}

		// 对每个桶进行排序
		buckets.forEach(bucket -> {
			Collections.sort(bucket);
		});

		int index = 0;
		for (ArrayList<Integer> bucket : buckets) {
			for (Integer elem : bucket) {
				data[index++] = elem;
			}
		}
	}

}
